from typing import *
from leetcode.editor.common.node import *


# leetcode submit region begin(Prohibit modification and deletion)
class Solution:
    def checkInclusion(self, s1: str, s2: str) -> bool:
        left, right = 0, 0
        need = {}
        for i in s1:
            need[i] = need.get(i, 0) + 1
        window = {}
        valid = 0
        while right < len(s2):
            r = s2[right]
            right += 1
            if r in need:
                window[r] = window.get(r, 0) + 1
                if window[r] == need[r]:
                    valid += 1
            if right - left >= len(s1):
                if valid == len(need):
                    return True
                l = s2[left]
                left += 1
                if l in need:
                    if window[l] == need[l]:
                        valid -= 1
                    window[l] = window.get(l, 0) - 1
        return False


# leetcode submit region end(Prohibit modification and deletion)


if __name__ == '__main__':
    solution = Solution()
    print(solution.checkInclusion("ab","eidbaooo"))
    # your test code here